package arithmetic.leetCode.yi;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yilin
 * Date: 2019-07-16
 * Time: 17:29
 */
public class Sqrt {
    public static void main(String[] args) {
        System.out.println(mySqrt(8));
    }

    public static int mySqrt(int x) {
        int left = 0, right = x / 2 + 1;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (mid * mid == x) {
                return (int) mid;
            } else if (mid * mid < x) {
                left = (int) (mid + 1);
            } else {
                right = (int) (mid - 1);
            }

        }
        return right;
    }

    double sqrt2() {
        double EPSINON = 0.0000000001;
        double left = 1.4;
        double right = 1.5;
        double mid = (left + right) / 2;

        while (right - left > EPSINON) {
            if (mid * mid > 2) {
                right = mid;
            } else {
                left = mid;
            }
            mid = (left + right) / 2;
        }
        return mid;
    }

}
